#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <time.h>

#include "skip_list.h"

#define NIVEAU_MAX 5


struct noeud {
    int valeur;
    noeud* suiv;
};

struct skiplist{
    noeud tete;
    int niveau;
};

int getNiveau(skiplist s){

  return s->niveau;
}

static noeud creer_noeud(int niveau, int valeur) 
{
  noeud n = malloc(sizeof(struct noeud));
  //n->suiv = memoire_allouer((niveau+1)*sizeof(noeud*));
  n->suiv = (noeud*)calloc(niveau + 1, sizeof(noeud));
  n->valeur = valeur;
  //n->suiv = NULL;  

  return n;
}

skiplist creer_skiplist() {
  skiplist s = malloc(sizeof(skiplist));
  s->tete = creer_noeud(NIVEAU_MAX, 0);
  s->niveau = 0;
  return s;
}

void afficher_skiplist(skiplist s) {
  noeud p = s->tete->suiv[0];
  while(p != NULL) {
    printf("%d ", p->valeur);
    p = p->suiv[0];
  }    
  printf("\n");
}

/*void afficher_complet_skiplist(skiplist s){
  
  noeud n = s->tete->suiv[0];
  while(n != NULL)
    {
      printf("%d\t", n->valeur);

      int i = 0;
      while(n->suiv[i] != NULL && i < s->niveau)
        {
          printf("X");
          i++;
        }
      for(; i < s->niveau; i++)
        printf("|");

      printf("\n");
      n = n->suiv[0];
    }
    }*/

bool est_dans_la_liste(skiplist s, int valeur) {
  noeud n = s->tete;
  for(int i = s->niveau; i >= 0; i--) {
    while(n->suiv[i] != NULL && n->suiv[i]->valeur < valeur) {
      n = n->suiv[i];
    }
  }
  n = n->suiv[0];
  
  return (n != NULL && n->valeur == valeur);
}

void effacer(skiplist s, int valeur) {
  int i;
  noeud n = s->tete;	
  noeud maj[NIVEAU_MAX + 1];
  memset(maj, 0, NIVEAU_MAX + 1);
  
  
  for(i = s->niveau; i >= 0; i--) {
    while(n->suiv[i] != NULL && n->suiv[i]->valeur < valeur) {
      n = n->suiv[i];
    }
    maj[i] = n; 
  }
  n = n->suiv[0];
  
  
  if(n->valeur == valeur) {
    for(i = 0; i <= s->niveau; i++) {
      if(maj[i]->suiv[i] != n)
	break;
      maj[i]->suiv[i] = n->suiv[i];
    }
    
    free(n);
    while(s->niveau > 0 && s->tete->suiv[s->niveau] == NULL) {
      s->niveau--;
    }
    
  }
}

static int niveau_aleatoire(){
  srand(time(NULL));
  int r = (rand() % NIVEAU_MAX) + 1; //genere un entier entre 1 et
				     //NIVEAU_MAX aleatoirement
  return r;
}

void inserer(skiplist s, int valeur) {
  int i;
  noeud n = s->tete;	
  noeud maj[NIVEAU_MAX + 1];
  memset(maj, 0, NIVEAU_MAX + 1);
  
  
  for(i = s->niveau; i >= 0; i--) {
    while(n->suiv[i] != NULL && n->suiv[i]->valeur < valeur) {
      n = n->suiv[i];
    }
    maj[i] = n; 
  }
  n = n->suiv[0];
  
  
  if(n == NULL || n->valeur != valeur) {        
    int lvl = niveau_aleatoire();
    
    if(lvl > s->niveau) {
      for(i = s->niveau + 1; i <= lvl; i++) {
	maj[i] = s->tete;
      }
      s->niveau = lvl;
    }
    
    n = creer_noeud(lvl, valeur);
    for(i = 0; i <= lvl; i++) {
      n->suiv[i] = maj[i]->suiv[i];
      maj[i]->suiv[i] = n;
    }
    
  }
}

